#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;	//数据元素中数据的类型
typedef struct node		//数据节点的类型
{
	ElemType data;	    //数据域 --》存储数据
	struct node *next;	//指针域 --》保存逻辑上的下一个
	struct node *prev;	//保存逻辑上的上一个
}DNODE;
				
typedef struct List		//头节点的类型
{
	struct node * first;//指向第一个节点
	struct node * last;//指向最后一个节点
	int node_num;	  //保存数据节点的个数
}DLIST;

//创建双向链表
DLIST * CreateDoubleList()//头结点和节点数
{
	//1.创建一个头节点，并初始化
	DLIST *head=(DLIST*)malloc(sizeof(DLIST));
	head->first=NULL;
	head->last=NULL;
	head->node_num=0;

	DNODE *pnew=NULL;
	ElemType data;
	while(1)
	{
		//2.从键盘中获取数据
		scanf("%d",&data);
		//规定0退出
		if(data==0)
		{
			break;
		}
		//3.创建节点，把数据写入到创建的数据节点中去
		pnew=(DNODE*)malloc(sizeof(DNODE));
		pnew->data=data;
		pnew->next=NULL;
		pnew->prev=NULL;
		//4.把新节点添加到双向链表中去
		if(head->first==NULL)//从无到有
		{
			head->first=pnew;
			head->last=pnew;
		}
		else//从少到多
		{
			//尾插法
			head->last->next=pnew;
			pnew->prev=head->last;
			//指向最后一个节点的指针域变换
			head->last=pnew;

			//头插法
			/*
			pnew->next=head->first;
			head->first->prev=pnew;
			head->first=pnew;
			*/
		}
		head->node_num++;
	}
	return head;
}

DLIST *DeleteNode(DLIST *head,int x)
{
	DNODE *p=head->first;
	while(p)
	{
		if(p->data==x)
		{
			p->prev->next=p->next;
			p->next->prev=p->prev;
			head->node_num--;
			if(head->node_num==0) break;
			free(p);
		}
		p=p->next;
	}
	return head;
}


//打印链表
void print_list(struct List *list)
{
	struct node * p = list->first;		//正向
	while(p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	putchar('\n');
	
	printf("======================================\n");
	p = list->last;					//逆向
	while(p)
	{
		printf("%d ", p->data);
		p = p->prev;
	}
	putchar('\n');
	printf("======================================\n");
}

int main()
{
	DLIST *head;
	head=CreateDoubleList();
	print_list(head);

	printf("请输入要删除的值:\n");
	int x;
	scanf("%d",&x);
	head=DeleteNode(head,x);
	print_list(head);
	return 0;
}
